home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / ip / ka9q / MNetsrc.hqx / Mac TCP_IP Source v.33 / iproute.c < prev    next >
Text File  |  1989-03-17  |  16KB  |  647 lines
  1. /* Lower half of IP, consisting of gateway routines
  2.  * Includes routing and options processing code
  3.  */
  4. #include "global.h"
  5. #include "config.h"
  6. #include "mbuf.h"
  7. #include "internet.h"
  8. #include "timer.h"
  9. #include "netuser.h"
  10. #include "ip.h"
  11. #include "icmp.h"
  12. #include "iface.h"
  13. #include "trace.h"
  14.  
  15. struct route *routes[32][NROUTE];    /* Routing table */
  16. struct route r_default;            /* Default route entry */
  17.  
  18. int32 ip_addr;
  19. struct ip_stats ip_stats;
  20.  
  21. #ifndef    GWONLY
  22. struct mbuf *loopq;    /* Queue for loopback packets */
  23. #endif
  24.  
  25. /* Route an IP datagram. This is the "hopper" through which all IP datagrams,
  26.  * coming or going, must pass.
  27.  *
  28.  * "rxbroadcast" is set to indicate that the packet came in on a subnet
  29.  * broadcast. The router will kick the packet upstairs regardless of the
  30.  * IP destination address.
  31.  */
  32. int
  33. ip_route(bp,rxbroadcast)
  34. struct mbuf *bp;
  35. char rxbroadcast;    /* True if packet had link broadcast address */
  36. {
  37.     struct mbuf *htonip();
  38.     void ip_recv();
  39.     struct ip ip;            /* IP header being processed */
  40.     int16 ip_len;            /* IP header length */
  41.     int16 length;            /* Length of data portion */
  42.     int32 gateway;            /* Gateway IP address */
  43.     register struct route *rp;    /* Route table entry */
  44.     struct interface *iface;    /* Output interface, possibly forwarded */
  45.     struct route *rt_lookup();
  46.     int16 offset;            /* Offset into current fragment */
  47.     int16 mf_flag;            /* Original datagram MF flag */
  48.     int strict = 0;            /* Strict source routing flag */
  49.     char precedence;        /* Extracted from tos field */
  50.     char delay;
  51.     char throughput;
  52.     char reliability;
  53.     int16 opt_len;        /* Length of current option */
  54.     char *opt;        /* -> beginning of current option */
  55.     char *ptr;        /* -> pointer field in source route fields */
  56.     struct mbuf *tbp;
  57. #ifdef PROXY
  58.     extern enable_is_es_arp();
  59. #endif
  60.  
  61.     ip_stats.total++;
  62.     if(len_mbuf(bp) < IPLEN){
  63.         /* The packet is shorter than a legal IP header */
  64.         ip_stats.runt++;
  65.         free_p(bp);
  66.         return -1;
  67.     }
  68.     /* Sneak a peek at the IP header's IHL field to find its length */
  69.     ip_len = (bp->data[0] & 0xf) << 2;
  70.     if(ip_len < IPLEN){
  71.         /* The IP header length field is too small */
  72.         ip_stats.length++;
  73.         free_p(bp);
  74.         return -1;
  75.     }
  76.     if(cksum(NULLHEADER,bp,ip_len) != 0){
  77.         /* Bad IP header checksum; discard */
  78.         ip_stats.checksum++;
  79.         free_p(bp);
  80.         return -1;
  81.     }
  82.     /* Extract IP header */
  83.     ntohip(&ip,&bp);
  84.  
  85.     if(ip.version != IPVERSION){
  86.         /* We can't handle this version of IP */
  87.         ip_stats.version++;
  88.         free_p(bp);
  89.         return -1;
  90.     }
  91.     /* Trim data segment if necessary. */
  92.     length = ip.length - ip_len;    /* Length of data portion */
  93.     trim_mbuf(&bp,length);    
  94.                 
  95.     /* Process options, if any. Also compute length of secondary IP
  96.      * header in case fragmentation is needed later
  97.      */
  98.     strict = 0;
  99.     for(opt = ip.options; opt < &ip.options[ip.optlen];opt += opt_len){
  100.         int32 get32();
  101.  
  102.         /* Most options have a length field. If this is a EOL or NOOP,
  103.          * this (garbage) value won't be used
  104.          */
  105.         opt_len = uchar(opt[1]);
  106.  
  107.         switch(opt[0] & OPT_NUMBER){
  108.         case IP_EOL:
  109.             goto no_opt;    /* End of options list, we're done */
  110.         case IP_NOOP:
  111.             opt_len = 1;
  112.             break;        /* No operation, skip to next option */
  113.         case IP_SSROUTE:    /* Strict source route & record route */
  114.             strict = 1;    /* note fall-thru */
  115.         case IP_LSROUTE:    /* Loose source route & record route */
  116.             /* Source routes are ignored unless we're in the
  117.              * destination field
  118.              */
  119.             if(ip.dest != ip_addr)
  120.                 break;    /* Skip to next option */
  121.             if(uchar(opt[2]) >= opt_len){
  122.                 break;    /* Route exhausted; it's for us */
  123.             }
  124.             /* Put address for next hop into destination field,
  125.              * put our address into the route field, and bump
  126.              * the pointer
  127.              */
  128.             ptr = opt + uchar(opt[2]) - 1;
  129.             ip.dest = get32(ptr);
  130.             put32(ptr,ip_addr);
  131.             opt[2] += 4;
  132.             break;
  133.         case IP_RROUTE:    /* Record route */
  134.             if(uchar(opt[2]) >= opt_len){
  135.                 /* Route area exhausted; kick back an error */
  136.                 union icmp_args icmp_args;
  137.  
  138.                 icmp_args.pointer = IPLEN + opt - ip.options;
  139.                 icmp_output(&ip,bp,PARAM_PROB,0,&icmp_args);
  140.                 free_p(bp);
  141.                 return -1;
  142.             }
  143.             /* Add our address to the route */
  144.             ptr = opt + uchar(opt[2]) - 1;
  145.             ptr = put32(ptr,ip_addr);
  146.             opt[2] += 4;
  147.             break;
  148.         }
  149.     }
  150. no_opt:
  151.  
  152.     /* See if it's a broadcast or addressed to us, and kick it upstairs */
  153.     if(ip.dest == ip_addr || rxbroadcast){
  154. #ifdef    GWONLY
  155.     /* We're only a gateway, we have no host level protocols */
  156.         if(!rxbroadcast)
  157.             icmp_output(&ip,bp,DEST_UNREACH,PROT_UNREACH,(union icmp_args *)NULL);
  158.         free_p(bp);
  159. #else
  160.  
  161.         /* If this is a local loopback packet, place on the loopback
  162.          * queue for processing in the main loop. This prevents the
  163.          * infinite stack recursion and other problems that would
  164.          * otherwise occur when we talk to ourselves, e.g., with ftp
  165.          */
  166.         if(ip.source == ip_addr){
  167.             /* Put IP header back on */
  168.             if((tbp = htonip(&ip,bp)) == NULLBUF){
  169.                 free_p(bp);
  170.                 return -1;
  171.             }
  172.             /* Copy loopback packet into new buffer.
  173.              * This avoids an obscure problem with TCP which
  174.              * dups its outgoing data before transmission and
  175.              * then frees it when an ack comes, even though the
  176.              * receiver might not have actually read it yet
  177.              */
  178.             bp = copy_p(tbp,len_mbuf(tbp));
  179.             free_p(tbp);
  180.             if(bp == NULLBUF)
  181.                 return -1;
  182.             enqueue(&loopq,bp);
  183.         } else {
  184.             ip_recv(&ip,bp,rxbroadcast);
  185.         }
  186. #endif
  187.         return 0;
  188.     }
  189.  
  190.     /* Decrement TTL and discard if zero */
  191.     if(--ip.ttl == 0){
  192.         /* Send ICMP "Time Exceeded" message */
  193.         icmp_output(&ip,bp,TIME_EXCEED,0,NULLICMP);
  194.         free_p(bp);
  195.         return -1;
  196.     }
  197.     /* Look up target address in routing table */
  198.     if((rp = rt_lookup(ip.dest)) == NULLROUTE){
  199.         /* No route exists, return unreachable message */
  200.         icmp_output(&ip,bp,DEST_UNREACH,HOST_UNREACH,NULLICMP);
  201.         free_p(bp);
  202.         return -1;
  203.     }
  204.     /* Check for output forwarding and divert if necessary */
  205.     iface = rp->interface;
  206.     if(iface->forw != NULLIF)
  207.         iface = iface->forw;
  208.  
  209.     /* Find gateway; zero gateway in routing table means "send direct" */
  210.     if(rp->gateway == (int32)0)
  211.         gateway = ip.dest;
  212.     else
  213.         gateway = rp->gateway;
  214.  
  215.     if(strict && gateway != ip.dest){
  216.         /* Strict source routing requires a direct entry */
  217.         icmp_output(&ip,bp,DEST_UNREACH,ROUTE_FAIL,NULLICMP);
  218.         free_p(bp);
  219.         return -1;
  220.     }
  221.     precedence = PREC(ip.tos);
  222.     delay = ip.tos & DELAY;
  223.     throughput = ip.tos & THRUPUT;
  224.     reliability = ip.tos & RELIABILITY;
  225.  
  226. #ifdef PROXY
  227.     if(gateway == ip.dest && ip.source != ip_addr){
  228.         /* The packet didnt originate from us and we're
  229.          * being used as a switch.  The next hop is to the
  230.          * final destination so set is_es arp to enable a
  231.          * return path.
  232.          */
  233.          enable_is_es_arp (ip.source, ip.dest, iface);
  234.         }
  235. #endif
  236.     if(ip.length <= iface->mtu){
  237.         /* Datagram smaller than interface MTU; put header
  238.          * back on and send normally
  239.          */
  240.         if((tbp = htonip(&ip,bp)) == NULLBUF){
  241.             free_p(bp);
  242.             return -1;
  243.         }
  244.         return (*iface->send)(tbp,iface,gateway,
  245.             precedence,delay,throughput,reliability);
  246.     }
  247.     /* Fragmentation needed */
  248.     if(ip.fl_offs & DF){
  249.         /* Don't Fragment set; return ICMP message and drop */
  250.         icmp_output(&ip,bp,DEST_UNREACH,FRAG_NEEDED,NULLICMP);
  251.         free_p(bp);
  252.         return -1;
  253.     }
  254.     /* Create fragments */
  255.     offset = (ip.fl_offs & F_OFFSET) << 3;
  256.     mf_flag = ip.fl_offs & MF;    /* Save original MF flag */
  257.     while(length != 0){        /* As long as there's data left */
  258.         int16 fragsize;        /* Size of this fragment's data */
  259.         struct mbuf *f_data;    /* Data portion of fragment */
  260.  
  261.         /* After the first fragment, should remove those
  262.          * options that aren't supposed to be copied on fragmentation
  263.          */
  264.         ip.fl_offs = offset >> 3;
  265.         if(length + ip_len <= iface->mtu){
  266.             /* Last fragment; send all that remains */
  267.             fragsize = length;
  268.             ip.fl_offs |= mf_flag;    /* Pass original MF flag */
  269.         } else {
  270.             /* More to come, so send multiple of 8 bytes */
  271.             fragsize = (iface->mtu - ip_len) & 0xfff8;
  272.             ip.fl_offs |= MF;
  273.         }
  274.         ip.length = fragsize + ip_len;
  275.  
  276.         /* Move the data fragment into a new, separate mbuf */
  277.         if((f_data = alloc_mbuf(fragsize)) == NULLBUF){
  278.             free_p(bp);
  279.             return -1;
  280.         }
  281.         f_data->cnt = pullup(&bp,f_data->data,fragsize);
  282.  
  283.         /* Put IP header back on */
  284.         if((tbp = htonip(&ip,f_data)) == NULLBUF){
  285.             free_p(f_data);
  286.             free_p(bp);
  287.             return -1;
  288.         }
  289.         /* and ship it out */
  290.         if((*iface->send)(tbp,iface,gateway,
  291.             precedence,delay,throughput,reliability) == -1)
  292.             return -1;
  293.  
  294.         offset += fragsize;
  295.         length -= fragsize;
  296.     }
  297.     return 0;
  298. }
  299.  
  300. struct rt_cache rt_cache;
  301.  
  302. /* Add an entry to the IP routing table. Returns 0 on success, -1 on failure */
  303. int
  304. rt_add(target,bits,gateway,metric,interface)
  305. int32 target;        /* Target IP address prefix */
  306. unsigned int bits;    /* Size of target address prefix in bits (0-32) */
  307. int32 gateway;
  308. int metric;
  309. struct interface *interface;
  310. {
  311.     struct route *rp,**hp,*rt_lookup();
  312.     int16 hash_ip(),i;
  313.     int32 mask;
  314.  
  315.     if(interface == NULLIF)
  316.         return -1;
  317.  
  318.     rt_cache.target = 0;    /* Flush cache */
  319.  
  320.     /* Zero bits refers to the default route */
  321.     if(bits == 0){
  322.         rp = &r_default;
  323.     } else {
  324.         if(bits > 32)
  325.             bits = 32;
  326.  
  327.         /* Mask off don't-care bits */
  328.         mask = 0xffffffff;
  329.         for(i=31;i >= bits;i--)
  330.             mask <<= 1;
  331.  
  332.         target &= mask;
  333.         /* Search appropriate chain for existing entry */
  334.         for(rp = routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  335.             if(rp->target == target)
  336.                 break;
  337.         }
  338.     }
  339.     if(rp == NULLROUTE){
  340.         /* The target is not already in the table, so create a new
  341.          * entry and put it in.
  342.          */
  343.         if((rp = (struct route *)malloc(sizeof(struct route))) == NULLROUTE)
  344.             return -1;    /* No space */
  345.         /* Insert at head of table */
  346.         rp->prev = NULLROUTE;
  347.         hp = &routes[bits-1][hash_ip(target)];
  348.         rp->next = *hp;
  349.         if(rp->next != NULLROUTE)
  350.             rp->next->prev = rp;
  351.         *hp = rp;
  352.     }
  353.     rp->target = target;
  354.     rp->gateway = gateway;
  355.     rp->metric = metric;
  356.     rp->interface = interface;
  357.  
  358.     return 0;
  359. }
  360.  
  361. /* Remove an entry from the IP routing table. Returns 0 on success, -1
  362.  * if entry was not in table.
  363.  */
  364. int
  365. rt_drop(target,bits)
  366. int32 target;
  367. unsigned int bits;
  368. {
  369.     register struct route *rp;
  370.     struct route *rt_lookup();
  371.     unsigned int i;
  372.     int16 hash_ip();
  373.     int32 mask;
  374.  
  375.     rt_cache.target = 0;    /* Flush the cache */
  376.  
  377.     if(bits == 0){
  378.         /* Nail the default entry */
  379.         r_default.interface = NULLIF;
  380.         return 0;
  381.     }
  382.     if(bits > 32)
  383.         bits = 32;
  384.  
  385.     /* Mask off don't-care bits */
  386.     mask = 0xffffffff;
  387.     for(i=31;i >= bits;i--)
  388.         mask <<= 1;
  389.  
  390.     target &= mask;
  391.  
  392.     /* Search appropriate chain for existing entry */
  393.     for(rp = routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  394.         if(rp->target == target)
  395.             break;
  396.     }
  397.     if(rp == NULLROUTE)
  398.         return -1;    /* Not in table */
  399.  
  400.     if(rp->next != NULLROUTE)
  401.         rp->next->prev = rp->prev;
  402.     if(rp->prev != NULLROUTE)
  403.         rp->prev->next = rp->next;
  404.     else
  405.         routes[bits-1][hash_ip(target)] = rp->next;
  406.  
  407.     free((char *)rp);
  408.     return 0;
  409. }
  410.  
  411. /* Compute hash function on IP address */
  412. static int16
  413. hash_ip(addr)
  414. register int32 addr;
  415. {
  416.     register int16 ret;
  417.  
  418.     ret = hiword(addr);
  419.     ret ^= loword(addr);
  420.     ret %= NROUTE;
  421.     return ret;
  422. }
  423. #ifndef    GWONLY
  424. /* Given an IP address, return the MTU of the local interface used to
  425.  * reach that destination. This is used by TCP to avoid local fragmentation
  426.  */
  427. int16
  428. ip_mtu(addr)
  429. int32 addr;
  430. {
  431.     register struct route *rp;
  432.     struct route *rt_lookup();
  433.     struct interface *iface;
  434.  
  435.     rp = rt_lookup(addr);
  436.     if(rp == NULLROUTE || rp->interface == NULLIF)
  437.         return 0;
  438.  
  439.     iface = rp->interface;
  440.     if(iface->forw != NULLIF)
  441.         return iface->forw->mtu;
  442.     else
  443.         return iface->mtu;
  444. }
  445. #endif
  446. /* Look up target in hash table, matching the entry having the largest number
  447.  * of leading bits in common. Return default route if not found;
  448.  * if default route not set, return NULLROUTE
  449.  */
  450. static struct route *
  451. rt_lookup(target)
  452. int32 target;
  453. {
  454.     register struct route *rp;
  455.     int16 hash_ip();
  456.     int bits;
  457.     int32 tsave;
  458.     int32 mask;
  459.  
  460.     if(target == rt_cache.target)
  461.         return rt_cache.route;
  462.  
  463.     tsave = target;
  464.  
  465.     mask = ~0;    /* All ones */
  466.     for(bits = 31;bits >= 0; bits--){
  467.         target &= mask;
  468.         for(rp = routes[bits][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  469.             if(rp->target == target){
  470.                 /* Stash in cache and return */
  471.                 rt_cache.target = tsave;
  472.                 rt_cache.route = rp;
  473.                 return rp;
  474.             }
  475.         }
  476.         mask <<= 1;
  477.     }
  478.     if(r_default.interface != NULLIF){
  479.         rt_cache.target = tsave;
  480.         rt_cache.route = &r_default;
  481.         return &r_default;
  482.     } else
  483.         return NULLROUTE;
  484. }
  485. /* Convert IP header in host format to network mbuf */
  486. struct mbuf *
  487. htonip(ip,data)
  488. struct ip *ip;
  489. struct mbuf *data;
  490. {
  491.     int16 hdr_len;
  492.     struct mbuf *bp;
  493.     register char *cp;
  494.     int16 checksum;
  495.  
  496.     hdr_len = IPLEN + ip->optlen;
  497.     if((bp = pushdown(data,hdr_len)) == NULLBUF){
  498.         free_p(data);
  499.         return NULLBUF;
  500.     }
  501.     cp = bp->data;
  502.     
  503.     *cp++ = (IPVERSION << 4) | (hdr_len >> 2);
  504.     *cp++ = ip->tos;
  505.     cp = put16(cp,ip->length);
  506.     cp = put16(cp,ip->id);
  507.     cp = put16(cp,ip->fl_offs);
  508.     *cp++ = ip->ttl;
  509.     *cp++ = ip->protocol;
  510.     cp = put16(cp,0);    /* Clear checksum */
  511.     cp = put32(cp,ip->source);
  512.     cp = put32(cp,ip->dest);
  513.     if(ip->optlen != 0)
  514.         memcpy(cp,ip->options,ip->optlen);
  515.  
  516.     /* Compute checksum and insert into header */
  517.     checksum = cksum(NULLHEADER,bp,hdr_len);
  518.     put16(&bp->data[10],checksum);
  519.  
  520.     return bp;
  521. }
  522. /* Extract an IP header from mbuf */
  523. int
  524. ntohip(ip,bpp)
  525. struct ip *ip;
  526. struct mbuf **bpp;
  527. {
  528.     char v_ihl;
  529.     int16 ihl;
  530.  
  531.     v_ihl = pullchar(bpp);
  532.     ip->version = (v_ihl >> 4) & 0xf;
  533.     ip->tos = pullchar(bpp);
  534.     ip->length = pull16(bpp);
  535.     ip->id = pull16(bpp);
  536.     ip->fl_offs = pull16(bpp);
  537.     ip->ttl = pullchar(bpp);
  538.     ip->protocol = pullchar(bpp);
  539.     (void)pull16(bpp);    /* Toss checksum */
  540.     ip->source = pull32(bpp);
  541.     ip->dest = pull32(bpp);
  542.  
  543.     ihl = (v_ihl & 0xf) << 2;
  544.     if(ihl < IPLEN){
  545.         /* Bogus packet; header is too short */
  546.         return -1;
  547.     }
  548.     ip->optlen = ihl - IPLEN;
  549.     if(ip->optlen != 0)
  550.         pullup(bpp,ip->options,ip->optlen);
  551.  
  552.     return ip->optlen + IPLEN;
  553. }
  554. /* Perform end-around-carry adjustment */
  555. int16
  556. eac(sum)
  557. register int32 sum;    /* Carries in high order 16 bits */
  558. {
  559.     register int16 csum;
  560.  
  561.     while((csum = sum >> 16) != 0)
  562.         sum = csum + (sum & 0xffffL);
  563.     return (int16) (sum & 0xffffl);    /* Chops to 16 bits */
  564. }
  565. /* Checksum a mbuf chain, with optional pseudo-header */
  566. int16
  567. cksum(ph,m,len)
  568. struct pseudo_header *ph;
  569. register struct mbuf *m;
  570. int16 len;
  571. {
  572.     register unsigned int cnt, total;
  573.     register int32 sum, csum;
  574.     register char *up;
  575.     int16 csum1;
  576.     int swap = 0;
  577.     int16 lcsum();
  578.  
  579.     sum = 0l;
  580.  
  581.     /* Sum pseudo-header, if present */
  582.     if(ph != NULLHEADER){
  583.         sum = hiword(ph->source);
  584.         sum += loword(ph->source);
  585.         sum += hiword(ph->dest);
  586.         sum += loword(ph->dest);
  587.         sum += uchar(ph->protocol);
  588.         sum += ph->length;
  589.     }
  590.     /* Now do each mbuf on the chain */
  591.     for(total = 0; m != NULLBUF && total < len; m = m->next) {
  592.         cnt = min(m->cnt, len - total);
  593.         up = (char *)m->data;
  594.         csum = 0;
  595.  
  596.         if(((long)up) & 1){
  597.             /* Handle odd leading byte */
  598.             if(swap)
  599.                 csum = uchar(*up++);
  600.             else
  601.                 csum = (int16)(uchar(*up++) << 8);
  602.             cnt--;
  603.             swap = !swap;
  604.         }
  605.         if(cnt > 1){
  606.             /* Have the primitive checksumming routine do most of
  607.              * the work. At this point, up is guaranteed to be on
  608.              * a short boundary
  609.              */
  610.             csum1 = lcsum((unsigned short *)up, cnt >> 1);
  611.             if(swap)
  612.                 csum1 = (csum1 << 8) | (csum1 >> 8);
  613.             csum += csum1;
  614.         }
  615.         /* Handle odd trailing byte */
  616.         if(cnt & 1){
  617.             if(swap)
  618.                 csum += uchar(up[--cnt]);
  619.             else
  620.                 csum += (int16)(uchar(up[--cnt]) << 8);
  621.             swap = !swap;
  622.         }
  623.         sum += csum;
  624.         total += m->cnt;
  625.     }
  626.     /* Do final end-around carry, complement and return */
  627.     return ~eac(sum) & 0xffff;
  628. }
  629. /* Machine-independent, alignment insensitive network-to-host long conversion */
  630. static int32
  631. get32(cp)
  632. register char *cp;
  633. {
  634.     int32 rval;
  635.  
  636.     rval = uchar(*cp++);
  637.     rval <<= 8;
  638.     rval |= uchar(*cp++);
  639.     rval <<= 8;
  640.     rval |= uchar(*cp++);
  641.     rval <<= 8;
  642.     rval |= uchar(*cp);
  643.  
  644.     return rval;
  645. }
  646.  
  647.